1. Field of the Invention
The present invention relates to a computer system, and deals more particularly with a method, system, and computer program product for encoding (and subsequently decoding) a sequence of periodic byte values that have a vertical correlation (e.g. so that they can be more efficiently stored and/or electronically transmitted for use in a real-time system or resource-constrained system).
2. Description of the Related Art
There are many computing applications for which the delivery time of electronically-transmitted information is critical. Processing time for the received information may also be critical in these applications, and for that matter, processing time may be critical in applications where delivery time is not an issue. Examples of computing applications where delivery and processing time are both typically sensitive to particular constraints include real-time systems such as computer-controlled robots, air-traffic control systems, and so forth. In some computing devices, the memory and/or storage resources (hereinafter referred to as memory resources) used by computing applications are also of critical importance, especially with the on-going trend for smaller and smaller computing devices (such as handheld or wearable computers, Web-enabled cellular phones, etc.).
By way of review, real-time systems are those in which an executing application must respond to incoming events within some time period imposed by external constraints (which are typically application-specific). In the case of a computer-controlled robot, for example, it may be necessary to ensure that the robot""s arm moves to a particular location before a widget is released at that location. Thus, the instructions that tell the robot to move its arm and the positional information that conveys the target destination must be received and processed by the time the widget is released. As another example, a graphics-intensive application such as a computer-generated movie animation, a virtual reality simulator, or a time-lapse weather map that graphically simulates changing weather conditions may need to receive and process new information very rapidly in order to generate a display with smooth transitions and no unnatural xe2x80x9cjerkinessxe2x80x9d.
For purposes of the present invention, any systems and applications having the types of information receipt, processing, and/or storage constraints that have been described will be referred to hereinafter as xe2x80x9creal-time systemsxe2x80x9d and xe2x80x9creal-time applicationsxe2x80x9d for ease of reference. Furthermore, the terms xe2x80x9creal-time applicationsxe2x80x9d and xe2x80x9creal-time systemsxe2x80x9d are used interchangeably hereinafter, unless otherwise stated, when referring to these types of applications and the systems on which they execute.
When an application has information receipt and/or processing time constraints, one way to ensure that the application will meet those constraints is to reduce the amount of information transmitted to it (e.g. by transmitting less frequently). However, this is not always a practical solution. In the case of robots, for example, reducing the amount of information may result in jerky movements: while this result may be tolerable if the robot is designed to clean a factory floor, it is not acceptable for other applications such as robotically-performed surgery.
One common measure used by real-time systems is the xe2x80x9cperiodxe2x80x9d of a particular task. The period is an interval of time representing the natural frequency of execution of that task. In the case of the virtual reality simulator, for example, the application may be designed to receive and process information some number of times per second, where the particular number is designed to enable a perceiving human user to believe that the simulation does in fact model the real world. This particular number is then a period of the simulator application. (Distinct periods may exist for different types of data input used by an application.) When the period can be reduced, information of a finer granularity can be sent to and processed by the simulator, resulting in a more realistic result. However, it may happen that the computing system on which the simulator application executes does not have sufficient storage for very fine-grained information; or, the volume of data transmitted may overrun the application""s or system""s processing capability. Therefore, in this virtual reality scenario (as well as in other real-time scenarios), it is important that the flow of input (i.e. control) information is optimized to ensure that processing and usage of memory resources are efficient.
Accordingly, what is needed is an improved technique for sending information to applications that may be constrained as to delivery time, processing time, and/or memory.
An object of the present invention is to provide an improved technique for sending information to systems and applications that may be resource-constrained.
Another object of the present invention is to provide a technique for sending information to systems and applications where delivery time, processing time, and/or memory resources must be optimized.
Another object of the present invention is to provide a technique for efficiently encoding information into a compressed format.
Yet another object of the present invention is to provide an improved technique for encoding information that is to be transmitted, processed, and/or stored in a computing system.
Still another object of the present invention is to provide an improved technique for encoding information that has a vertical correlation among particular values.
A further object of the present invention is to provide an encoding technique that enables resource-constrained systems to handle finer-granularity information.
Other objects and advantages of the present invention will be set forth in part in the description and in the drawings which follow and, in part, will be obvious from the description or may be learned by practice of the invention.
To achieve the foregoing objects, and in accordance with the purpose of the invention as broadly described herein, the present invention provides a method, system, and computer program product for efficiently encoding a sequence of data values that have a vertical correlation. This technique comprises: accessing a plurality of data values, wherein the plurality of data values is logically structured as a plurality of rows, each of the rows having a plurality of columns; and encoding the plurality of data values as a compressed output stream. The encoding further comprises: omitting selected ones of the plurality of data values from the output stream, wherein the selected ones are those data values which are repeated from one column in one row to that column in a next-sequential row; and indicating the omission in the output data stream without loss of information content.
The technique may further comprise transmitting the compressed output stream to a receiver. In this case, the technique may also comprise: receiving, at the receiver, the transmitted output stream; and decoding the received output stream into the logical structure of the plurality of rows and the plurality of columns. The decoded output stream may then be used as periodic input for an application. The application may be a real-time application.
The encoding may further comprise: creating a marker byte to indicate how many sequential rows have identical data values in each column; creating a bit mask for each row that has changed data values, wherein one or more bits in the bit mask are set on for each column in the row which has one of the changed data values; and writing the marker bytes and the bit masks into the output stream, along with the changed data values.
The data values may be byte values. Each of the rows preferably represents a periodic set of data values.
The present invention will now be described with reference to the following drawings, in which like reference numbers denote the same element throughout.